package liecai_class.day03;

import java.util.Arrays;

/**
 * 归并排序
 *
 * 利用归并思想实现的排序方法, 该算法采用了经典的分治策略
 */
public class ArraySort06 {
    public static void main(String[] args) {
        int[] arr = {3,5,2,7,9,1,4,6,8};
        System.out.println("数组: "+ Arrays.toString(arr));
        mergeSort(arr,0,arr.length/2,arr.length-1);
        System.out.println("排序后: "+Arrays.toString(arr));

    }
    private static void mergeSort(int[] arr, int low, int mid, int high){
        int[] temp = new int[high-low+1];

        int left = low;
        int right = mid+1;

        int index = 0;

        while(left<=mid && right<=high){
            if (arr[left]<=arr[right]){
                temp[index] = arr[left];
                left++;
                index++;
            }else{
                temp[index] = arr[right];
                right++;
                index++;
            }
        }

        while (left<=high){
            temp[index] = arr[left];
            index++;
            left++;
        }

        while (right<=high){
            temp[index] = arr[right];
            index++;
            right++;
        }

        for (int x=0;x<temp.length;x++){
            arr[low+x] = temp[x];
        }
    }
}
